package cn.chen.数据结构.二叉树;

/**
 * 二叉排序树：左子节点小于根结点小于右子节点
 */
public class BinaryTree {

    private TreeNode root;  // 根结点

    public void setRoot(TreeNode root) {
        this.root = root;
    }
    public TreeNode getRoot() {
        return root;
    }

    public void addNode(TreeNode rt,TreeNode node){

        if(isEmpty()){  // 根结点为空，那么就将该节点作为根结点

            if(node!=null)
                setRoot(node);
            return;
        }
        // 根结点不为空
        if(rt!=null&&node!=null){

            if(node.id<rt.id){

                if(rt.leftNode==null)   // rt 的左子节点为空，那么就直接放在左子树就可以了
                    rt.leftNode=node;
                else                    // rt 的左子节点不为空，那么就递归
                    addNode(rt.leftNode,node);
            }
            if(node.id==rt.id)
                throw new RuntimeException("该元素已经存在，不能添加");

            if(node.id>rt.id) {

                if(rt.rightNode==null)
                    rt.rightNode = node;
                else
                    addNode(rt.rightNode,node);
            }
        }
    }
    // 判断该二叉树是否为空
    public boolean isEmpty(){

        return this.root==null;
    }

    // 前序查找
    /**
     *
     * @param rt    将在该节点作为根结点的树中进行比较
     * @param id    要查找的id值
     * @return      查找到的节点，查找不到就是null
     */
    public TreeNode preSelect(TreeNode rt,int id){

        System.out.println("--");
        if(rt==null)
            return null;

        if(rt.id==id)
            return rt;

        // 在左子节点和右子节点中判断rt.id与id的大小，可以确保只会进入左子节点或者右子节点，并且进入一边之后就会找到结果，如果找不到结果那么就是没有结果。
        if(rt.leftNode!=null&&rt.id>id)     // 左子节点不为空，并且要查询的id比当前节点小，才往左边遍历，这里要么找到，要么找不到。
            return preSelect(rt.leftNode,id);

        if(rt.rightNode!=null&&rt.id<id)    // 右子节点不为空，并且要查询的id比当前节点大，才往右边遍历，节约时间
            return preSelect(rt.rightNode,id);
        return null;    // 没有找到
    }
    // 中序查找
    public TreeNode midSelect(TreeNode rt,int id){

        if(rt==null)
            return null;

        if(rt.leftNode!=null&&rt.id>id)
            return midSelect(rt.leftNode,id);

        if(rt.id==id)
            return rt;

        if(rt.rightNode!=null&&rt.id<id)
            return midSelect(rt.rightNode,id);
        return null;
    }
    // 后序查找
    public TreeNode postSelect(TreeNode rt,int id){

        if(rt==null)
            return null;

        if(rt.leftNode!=null&&rt.id>id)
            return postSelect(rt.leftNode,id);

        if(rt.rightNode!=null&&rt.id<id)
            return postSelect(rt.rightNode,id);

        if(rt.id==id)
            return rt;
        return null;
    }


    // 递归前序遍历
    public void preOrder(TreeNode node){

        // 1、输出根结点
        System.out.println(node.toString());

        // 2、如果左子节点不为空，就递归前序遍历
        if(node.leftNode!=null)
            preOrder(node.leftNode);

        // 3、如果右子节点不为空，就递归前序遍历
        if(node.rightNode!=null)
            preOrder(node.rightNode);
    }

    // 递归中序遍历
    public void midOrder(TreeNode node){

        // 1、如果左子节点不为空，就递归中序遍历
        if(node.leftNode!=null)
            midOrder(node.leftNode);

        // 2、输出当前节点
        System.out.println(node.toString());

        // 3、如果右子节点不为空，就递归中序遍历
        if(node.rightNode!=null)
            midOrder(node.rightNode);
    }

    // 递归后序遍历
    public void postOrder(TreeNode node){

        // 1、如果左子节点不为空，就递归后序遍历
        if(node.leftNode!=null)
            postOrder(node.leftNode);

        // 3、如果右子节点不为空，就递归后序遍历
        if(node.rightNode!=null)
            postOrder(node.rightNode);

        // 2、输出当前节点
        System.out.println(node.toString());
    }
}

